题面

求一段区间的权值 $=length\times value$ 的 $max$ 值题目

解题思路

方法一：ST表+倍增+贪心

显然：

  1. 如果区间左端点 $l$ 确定，该区间可能的 $gcd$ 取值最多只有 $log_2a_l$ 种
  2. 如果 $gcd$ 确定，区间长度越长，答案越优

如此一来，我们就可以枚举 $l$，用倍增求每一个 $gcd$ 可能值的最右端点 $r$，由于随着 $r$ 的变化，$gcd$ 的取值最多有 $log_2a_l$ 种，就算乘上倍增的 $log_2(n-l+1)+1$ ，复杂度也是允许的，只需用 $ST$ 表事先处理区间 $gcd$ 即可

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline LL read() {
    rll s=0;rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,m,b[19],Log[N];LL f[N][19],ans,res;
inline LL calc(rint l,rint r) {
    rint k=Log[r-l+1];
    return __gcd(f[l][k],f[r-b[k]+1][k]);
}
inline void solve(rint l) {//分别求出每种gcd的左右端点
    rint k,r=l;LL c;
    while(r<=n) {
        for(k=Log[n-l+1],c=calc(l,r);k>=0;--k)
            if(r+b[k]-1<=n&&c==calc(l,r+b[k]-1)) r+=b[k];
        cmax(ans,c*(r-l));
    }
}
int main() {
    rint i,j;n=read(),Log[0]=-1,b[0]=1;
    for(i=1;i<=n;i++) f[i][0]=read(),Log[i]=Log[i>>1]+1;m=Log[n];
    for(i=1;i<=m;++i) b[i]=b[i-1]<<1;
    for(j=1;j<=m;j++)//ST表
        for(i=1;i+(1<<j)<=n+1;++i)
            f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for(i=1;i<=n;i++) solve(i);//枚举左端点
    printf("%lld",ans);
    return 0;
}

方法二：分治

这波是从题解学到的 下为原话

对于这类求一段区间的权值 $=length \times value$ 的 $max$ 或 $min$ 值题目，一般采取用分治的思想解决

设 $\large mid=\frac {l+r} 2$，则 $[l,mid]$ 与 $[mid+1,r]$ 合并时，一定会包含 $a_{mid}$

由于运用的是分治，我们可以参考归并排序中 $[a_l<b_r]$ 的 $cmp$ 条件

这里我们使用 $\large gcd(al,a{mid})$ 与 $\large gcd(ar,a{mid})$ 的大小关系作为拓展条件

以 $mid$ 为中心，将 $l,r$ 向 $gcd$ 较大的方向拓展，通过贪心可以证明这样的选法是更优的，每次计算得答案即可

时间复杂度（不算 $gcd$ 时间）为 $nlog_2n$

Code

当然是嫖的 $Link$

%:pragma GCC optimize(2)
%:pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define lll __int128

const int N = 100005;

ll a[N];
int n;

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll dfs(int l, int r) {
  if (l == r) return a[l];
  int mid = (l + r) >> 1;
  ll ans = max(dfs(l, mid), dfs(mid + 1, r));
  ll g = gcd(a[mid], a[mid + 1]);
  ans = max(ans, 2LL * g);

  int x = mid, y = mid + 1;
  while (x > l && y < r) {
    if (gcd(g, a[x - 1]) > gcd(g, a[y + 1])) {//选择拓展方向
      g = gcd(g, a[x - 1]); x--;
    }
    else {
      g = gcd(g, a[y + 1]); y++;
    }
    ans = max(ans, (ll)(y - x + 1) * g);
  } 
  while (x > l) {//可能一侧已经拓展完了
    g = gcd(g, a[x - 1]); x--;
    ans = max(ans, (ll)(y - x + 1) * g);
  }
  while (y < r) {
    g = gcd(g, a[y + 1]); y++;
    ans = max(ans, (ll)(y - x + 1) * g);
  }
  return ans;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  printf("%lld\n", dfs(1, n));
  return 0;
}

devil.